In an asynchronous spread spectrum (A-SS) system, as relative delays between signals transmitted can be arbitrary, it is desirable to find spreading sequences with low aperiodic autocorrelation functions (ACFs). Searching for binary sequences with low peak sidelobe level is a conventional problem that has raised computational challenges to researchers in this area, and the problem is sometimes referred to as the search for low-autocorrelation binary sequences (LABS). Among other uses, these binary sequences can be used for pulse compression in radar scenarios, channel synchronization and tracking, wireless CDMA communication, and theoretical physics.
Considering a binary sequence of length L, a=a1a2 . . . aL, its autocorrelation function (ACF) is given by equation (1):Ck(a)=Σi=1L−kaiai+k,ai={−1,+1},k=1, . . . ,L−1  (1)
The above definition for ACF of equation (1) can be extended to k=−L+1, . . . ,L−1. For instance, similar to equation (1), the aperiodic autocorrelation function can be defined according to equation (2):
                                          C            a                    ⁡                      (            t            )                          =                  {                                                                                                                ∑                                              n                        =                        0                                                                    L                        -                        t                        -                        1                                                              ⁢                                                                  a                        n                                            ⁢                                              a                                                  n                          +                          t                                                *                                                                              ,                                                                              0                  ≤                  t                  ≤                                      L                    -                    1                                                                                                                                                                  ∑                                              n                        =                        0                                                                    L                        -                        t                        +                        1                                                              ⁢                                                                  a                        n                                            ⁢                                              a                                                  n                          -                          t                                                *                                                                              ,                                                                                                  1                    -                    L                                    ≤                  t                  <                  0                                                                                                      0                  ,                                                                                                                      t                                                        ≥                  L                                                                                        (        2        )            where (.)* denotes conjugation (for cases when an is complex valued).
With reference to equation (1), at k=0, the peak ACF L is obtained, and the elements of ACF for k≠0 are called sidelobes. The peak sidelobe level (PSL) for length L is defined as equation (3):
                              PSL          L                =                              min                          a              ∈                                                {                                                            -                      1                                        ,                                          +                      1                                                        }                                L                                              ⁢                                    max                                                1                  ≤                  k                  ≤                                      L                    -                    1                                                  ,                                  k                  ≠                  0                                                      ⁢                                                                          C                  k                                ⁡                                  (                  a                  )                                                                                                      (        3        )            
Similarly, the PSL of a sequence a can be expressed as equation (4):
                                          PSL            ⁡                          (              a              )                                =                                    max                              1                ≤                t                ≤                                  L                  -                  1                                                      ⁢                                                                          ∑                                      n                    =                    0                                                        L                    -                    t                    -                    1                                                  ⁢                                                      a                    n                                    ⁢                                      a                                          n                      +                      t                                        *                                                                                                    ,                            (        4        )            
The merit factor, F of a, to denote a M-phase sequence has conventionally been defined by equation (5):
                              F          ⁡                      (            a            )                          =                              L            2                                2            ⁢                                          ∑                                  k                  =                  1                                                  L                  -                  1                                            ⁢                                                C                  k                  2                                ⁡                                  (                  a                  )                                                                                        (        5        )            
The sum term in the denominator of equation (5) is called the energy, with an as its n-th component, for n=0,1, . . . ,L−1, where L is the length of the sequence. The asymptotic value for the maximum F has been given as: F→12.3248 as L→∞. In this regard, sequence search attempts to find a sequence with minimum PSL or optimum F.
The LABS, or maximum merit factor, problem is a hard problem since there are numerous local minima as well as many optima. For example, a full exhaustive search for L=64 has yielded 14872 optimal-PSL codes and the optimal PSL is 4, even though these codes have a wide variability of merit factors. In this regard, a main problem is that the conventional gradient and other search approaches tend to become trapped in bad local minima. The aperiodic ACF of a length-L binary sequence has L−1 sidelobes that are not equivalent. A binary array of size K×K with L=K2 has 2K(K−1) sidelobes.
Both PSL and the merit factor F have been used as criteria for determining the quality of sequences. However, due to limitations on computational power, for a given temporal need or application requirement, it becomes harder to find optimal sequences for long sequence lengths because the search space S considered grows exponentially with the sequence length L. In order to find the sequences with lowest PSL with respect to their corresponding length L, the most direct way is exhaustive search. In total, however, experimental results of a total of 2L binary sequences of length L with O(L2) operations have to be computed algebraically to find the optimal sequences with exhaustive search—a large number with large length L.
Results for a branch-and-bound algorithm included report of a runtime complexity of O(1.85L) to find optimal merit factors for L≦60, while symmetry breaking procedures for identifying equivalent sequences allow the search space to be reduced to approximately one-eighth. A similar approach has been applied to exhaustive search. In addition, a sidelobe invariant tranform, a branch-and-merge search strategy, PSL-preserving operations, symmetry breaking, partitioning and parallelizing the search have been applied, further reducing the time complexity to O(1.4L) [4, 36].
Some exact values of best PSL have been found by exhaustive search and are summarized as follows:
1) PSL≦1 for L=2,3,4,5,7,11,13. These sequences are known as Barker sequences.
2) PSL≦2 for L≦21,
3) PSL≦3 for L≦48,
4) PSL≦4 for L≦70.
For odd L, a particular subclass of the skew-symmetric sequences has the property of an+i=(−1)i an−i, n=(L+1)/2, for i=1, . . . , n−1. For these sequences, Ck=0 for all odd k. Since the right half of the sequence is determined by the left half, sequence search is reduced to the general LABS problem for (L+1)/2. Searching the skew-symmetric sequences reduces the effect size of the sequence length by a factor of two. But for some values of L, it is noted energies are present well above the true ground state energy.
As further background, there are some special classes of low-autocorrelation binary sequences. Maximal-length shift register sequences (m-sequence) are pseudonoise (PN) sequences of length L=2n−1, n=1, 2, . . . , which can be generated by shift registers. Legendre sequences are another class of PN sequences. By presenting a method to generate Legendre sequences for prime lengths in the range of 67 to 1019, the computation of aperiodic ACF of cyclically shifted Legendre sequences has been performed, where, for larger L, the best known results can be achieved by periodically extending cyclically shifted Legendre sequences.
An integer programming method for the LABS problem at any L has computed PSL values and F (for L=71 through 100) of the sequences by using a Mixed-Integer Linear Programming (MILP) solver. In general, the minimal PSL values that are obtained are not better than the minimal PSL values obtained by an evolutionary algorithm (EA), but according to results, the integer programming method generates a lower PSL of 5 at L=74.
Some stochastic search methods such as simulated annealing (SA) or EAs can be applied for escaping local minima. One stochastic approach has reported a runtime complexity of O(1.68L). Compared to a Kernighan-Lin solver at O(1.463L) runtime, an evolutionary strategy (ES)-based search for optima may require significantly fewer samples (on average), e.g., O(1.397L) at runtime, as the problem size increases.
In some aspects, the performance of EAs is superior to other stochastic search algorithms. Popular conventional EAs are the genetic algorithm (GA), the evolutionary strategies (ES), and the memetic algorithm (MA).
For instance, one GA method that has been applied first generates a population of size P, then generates some offspring by one-point or two-point mutation, and others by one-point crossover. Unlike conventional GA approaches that use a proportional probabilistic selection mechanism, elistism is applied: P offspring with the best fitness are then selected as the parents in the next generation. For L≧71, due to the size of the length and associated complexity of computation, a number of non-exhaustive heuristic approaches, such as stochastic methods, genetic algorithm, integer programming method, have been proposed to search for sequences with minimal PSL. One example taking advantage of parallel processing with multiple cores, for sequences with lengths from 71 to 105, listed the following results:
5) PSL≦4 for 71≦L≦82,
6) PSL≦5 for 83≦L≦105.
Notwithstanding the above approaches, there is still no method other than exhaustive search that can give the exact minimal PSL among the whole search space Sε{−1,1}L. While high-performance parallel computing clusters could provide good results, these systematic search methods would still lack scalability to search for ever longer sequences without mathematical/algorithmic insights in a limited-resources (time and memory) scenario.
Some conventional heuristic methods for searching sequences with low autocorrelation sidelobes attempted to search for sequences above L=70. With the employment of EA in one such approach, binary sequences with acceptable aperiodic ACF have been obtained. First of all, the algorithm starts with initial random generation of parent sequences. Then, mutation and crossover are applied to generate a controllable number of children sequences and the following fitness function is used,
                                          f            1                    ⁡                      (            a            )                          =                              α                          PSL              ⁡                              (                a                )                                              +                      β            ⁢                                                  ⁢                          F              ⁡                              (                a                )                                                                        (        6        )            where α, β are scaling factors.
With respect to fitness, when α=0 and β≠0, the fitness function corresponds to minimum PSL; when α≠0 and β=0, the fitness function corresponds to the maximum F. A list of sequences of lengths 49-−100 is given. The obtained PSL values obtained were shown to be the same or better than the PSL values obtained using the Hopfield neural network for searching good binary sequences. In another EA approach, P parents are generated, and then O offspring are generated by one-point crossover; the P+O individuals compete and the P best individuals survive as next generation; one-point or two-point mutation is applied only when some of the P best individuals have the same fitness, or PSL.
In another approach, ES has been used for LABS for optimum F, where a preselection operation is applied to the generated individuals from mutation. The fitness is thus used for evaluating the performance of both parent and children sequences. Note that if α=0 and β≠0, the fitness function computes the values (performance) of sequences depending on the merit factor F only; on the other hand, if α≠0 and β=0, the sequences are evaluated towards their corresponding PSL only.
The MA has also been used for the LABS problem. In one approach, an ES is used as the EA, and a local search is implemented by flipping each bit of the string. The fitness function is selected as equation (7):
                                          f            2                    ⁡                      (            a            )                          =                              F            ⁡                          (              a              )                                            PSL            ⁡                          (              a              )                                                          (        7        )            
For this approach, the obtained F was greater that the above noted approach for L=71 to 100, but the PSL is typically worse. In yet another approach, the bit-flipping or tabu search is used as the local search, for maximizing F. The MA with tabu search is more effective in finding the optimum than the Kernighan-Lin and the MA with bit climber, from the experiments of L≦60. The MA with tabu search is an order of magnitude faster than the pure tabu search with frequent restarts, and the latter is roughly on par with Kernighan-Lin solver for the LABS problem, with respect to maximizing F. A multiobjective EA has also been used to generate complex spreading sequences with acceptable crosscorrelation and/or autocorrelation properties for some applications. The GA has also been used to generate acceptable training sequences for multiple antenna (spatial multiplexing) systems. In consideration of the various conventional approaches to generating or searching for LABs, an effective approach for generating long sequences, e.g., L>70, is desired under constrained circumstances where exhaustive search is not a realistic option, e.g., where time, processing capability, power and/or memory are constrained.
The above-described deficiencies are merely intended to provide an overview of some of the problems of conventional systems and techniques, and are not intended to be exhaustive. Other problems with conventional systems and techniques, and corresponding benefits of the various non-limiting embodiments described herein may become further apparent upon review of the following description.